import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;


public class ClusteringBig {	
	
	class Vertex{
		Vertex head;
		int data;
		int rank;
	}
	int count;
	int bits;
	ArrayList<Vertex> vertices;
	static int []mask;
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("C:\\workspace\\testdata\\clustering_big.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		count = Integer.parseInt(parser[0]);
		bits = Integer.parseInt(parser[1]);
		vertices = new ArrayList<Vertex>(count);		
		
		while((str = reader.GetNextLine()) != null)
		{
			Vertex v = new Vertex();
			v.head = v;
			v.rank = 0;
			parser = str.split(" ");
			
			for(int i = 0; i < bits; i++)
			{
				v.data = (v.data << 1) + Integer.parseInt(parser[i]);
			}
			
			vertices.add(v);
		}
		
		//init mask
		mask = new int[bits];
		for(int i = 0; i < bits; i++)
		{
			mask[i] = 1 << (bits - (i + 1));
		}
	}
	
	public void PrintData(){
		for(int i = 0; i < vertices.size(); i++)
		{
			Vertex v = vertices.get(i);
			Vertex head = this.GetHead(v);
			//System.out.println(v.data + "\t" + Integer.toBinaryString(v.data) + "\t" + head);
			//System.out.printf("%b\n", v.data);
		}
	}
	
	
	public void PrintCurrentTime(String strPrefix){
		System.out.println(strPrefix);
		SimpleDateFormat sf = new SimpleDateFormat("HH:mm:ss.SSS");
		System.out.println(sf.format(new Date()));
	}
	
	
	private boolean IsInSameGroup(Vertex v1, Vertex v2){
		Vertex head1 = GetHead(v1);		
		Vertex head2 = GetHead(v2);		
		
		if(head1 == head2)
			return true;
		else
			return false;
	}
	
	
	private Vertex GetHead(Vertex v)
	{
		Vertex head = v.head;
		Vertex t = v;
		while(head != t)
		{
			t = head;
			head = t.head;
		}
		
		t=v;
		while(t.head != head)
		{
			v = t.head;
			t.head = head;
			t = v;
		}
		return head;
	}
	
	private void MergeTwoGroups(Vertex v1, Vertex v2){
		//System.out.println("merge " + v1.data + "\t" + v2.data);
		Vertex head1 = GetHead(v1);
		Vertex head2 = GetHead(v2);
		
		if(head1.rank > head2.rank)
		{
			head2.head = head1;
		}
		else if(head1.rank == head2.rank)
		{
			head1.rank++;
			head2.head = head1;
		}
		else{
			head1.head = head2;
		}
	}
	
	public int[] GetVerticesLessEqual2(int v){
		int [] nearV = new int [bits + bits * (bits - 1) / 2];
		int cur = 0;
		
		for(int i = 0; i < mask.length; i++)
		{
			if((v & mask[i]) == 0){
				nearV[cur++] = v | mask[i];
				for(int j = i + 1; j < mask.length; j++)
				{
					if((v & mask[j]) == 0){
						nearV[cur++] = v | mask[i] | mask[j];
					}
					else{
						nearV[cur++] = (v | mask[i]) &(~mask[j]);
					}
				}
			}
		}
		return nearV;
	}
	
	public ArrayList<Vertex> SearchVertices(long data, int start){
		ArrayList<Vertex> result = new ArrayList<Vertex>(bits + bits * (bits - 1) / 2);
		
		//binary search
		int low = 0;
		int high = vertices.size() - 1;
		int foundIndex = -1;
		while(low <= high)
		{
			int mediumIndex = (low + high)/2;
			Vertex medium = vertices.get(mediumIndex);
			if(data == medium.data)
			{
				foundIndex = mediumIndex;
				break;
			}
			else if(data < medium.data)
			{
				high = mediumIndex - 1;
			}
			else
			{
				low = mediumIndex + 1;
			}
		}
		
		if(foundIndex != -1)
		{
			Vertex found = vertices.get(foundIndex);
			result.add(found);
			int i = 1;
			Vertex next;
			if(foundIndex - i > 0)
			{
				next = vertices.get(foundIndex - i);
				while(next.data == found.data )
				{
					result.add(next);
					i++;
					if(foundIndex - i > 0)
						next = vertices.get(foundIndex - i);
					else
						break;
				}
			}
			
			i = 1;
			if(foundIndex + i < count)
			{
				next = vertices.get(foundIndex + i);
				while(next.data == found.data)
				{
					result.add(next);
					i++;
					if(foundIndex - i < count)
						next = vertices.get(foundIndex + i);
					else 
						break;
				}
			}
		}
		
		return result;
	}
	
	
	public void RunClurstering(){
		this.PrintCurrentTime("start clustering computation");
		Collections.sort(vertices, new Comparator<Vertex>(){
			public int compare(Vertex v1, Vertex v2){
				if(v1.data > v2.data)
					return 1;
				else if(v1.data < v2.data)
					return -1;
				else 
					return 0;
			}
		});
		
		long k = count;
		
		for(int i = 0; i < count; i++)
		{
			Vertex v = vertices.get(i);
			Vertex v2;
			int j = i + 1;
			if(j < count)
			{
				v2 = vertices.get(j);
				while(v.data == v2.data)
				{
					i = j;
					if(!IsInSameGroup(v, v2))
					{
						MergeTwoGroups(v, v2);
						k--;
					}
					j++;
					if(j < count)
						v2 = vertices.get(j);
					else 
						break;
				}
			}
			//get all vertices within distance 1/2
			int []v2search = GetVerticesLessEqual2(v.data);
			//search all the vertices
			for(j = 0; j < v2search.length && v2search[j] != 0; j++)
			{
				//if found, might found multiple entry, if not in the same group, merge, k--
				//if found, if in the same group, do nothing
				//if not found, find the next one
				ArrayList<Vertex> entries = SearchVertices(v2search[j], i + 1);
				for(int l = 0; l < entries.size(); l++)
				{
					if(!IsInSameGroup(v, entries.get(l))){
						MergeTwoGroups(v, entries.get(l));
						k--;
					}
				}				
			}			
		}
		
		System.out.println("the clustering number is " + k);
		PrintCurrentTime("finish clustering computation");
	}
}
